package com.cuz.for2024;

import java.lang.reflect.Array;
import java.util.Arrays;

public class T91 {
    public static void main(String[] args) {
        System.out.println(new T91().numDecodings1("11106"));
        System.out.println(new T91().numDecodings1("12"));
        System.out.println(new T91().numDecodings1("06"));

        System.out.println("==");
        System.out.println(new T91().numDecodings2("11106"));
        System.out.println(new T91().numDecodings2("12"));
        System.out.println(new T91().numDecodings2("06"));

        System.out.println("==");
        System.out.println(new T91().numDecodings3("11106"));
        System.out.println(new T91().numDecodings3("12"));
        System.out.println(new T91().numDecodings3("06"));
    }

    public int numDecodings3(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] charArray = s.toCharArray();
        if (charArray[0] == '0') {
            return 0;
        }

        int next = charArray[charArray.length - 1] == '0' ? 0 : 1;
        int nextNext = 0;

        for (int index = charArray.length - 2; index >= 0; index--) {

            char nowChar = charArray[index];
            int temp = next;
            if (nowChar == '0') {
                temp = 0;
            } else {
                if (index + 1 < charArray.length) {
                    if ((charArray[index + 1] - '0') + (nowChar - '0') * 10 <= 26) {
                        temp += index + 2 >= charArray.length ? 1 : nextNext;
                    }
                }
            }

            nextNext = next;
            next = temp;
        }
        return next;
    }

    public int numDecodings2(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] charArray = s.toCharArray();
        if (charArray[0] == '0') {
            return 0;
        }
        int[] dp = new int[charArray.length];
        dp[charArray.length - 1] = charArray[charArray.length - 1] == '0' ? 0 : 1;
        for (int index = charArray.length - 2; index >= 0; index--) {
            char nowChar = charArray[index];
            if (nowChar == '0') {
                dp[index] = 0;
                continue;
            }
            dp[index] = dp[index + 1];
            if (index + 1 < charArray.length) {
                if ((charArray[index + 1] - '0') + (nowChar - '0') * 10 <= 26) {
                    dp[index] += index + 2 >= dp.length ? 1 : dp[index + 2];
                }
            }
        }
        return dp[0];
    }

    public int numDecodings1(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] charArray = s.toCharArray();
        if (charArray[0] == '0') {
            return 0;
        }

        int[] cached = new int[charArray.length];
        Arrays.fill(cached, -1);
        return process(charArray, 0, cached);
    }

    private int process(char[] charArray, int i, int[] cached) {
        if (i >= charArray.length) {
            return 1;
        }
        char nowChar = charArray[i];
        if (nowChar == '0') {
            return 0;
        }
        if (cached[i] != -1) {
            return cached[i];
        }
        int ans = process(charArray, i + 1, cached);
        if (i + 1 < charArray.length) {
            if ((charArray[i + 1] - '0') + (nowChar - '0') * 10 <= 26) {
                ans += process(charArray, i + 2, cached);
            }
        }
        cached[i] = ans;
        return ans;
    }
}
